#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
static char buf[1000000],*p1=buf,*p2=buf;
#define GC()	(p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++)
#define PC(x)	putchar(x)
int read(){
	int x = 0; char c = GC();
	while(c < '0' || c > '9') c = GC();
	while(c >= '0' && c <= '9'){
		x = (x << 3) + (x << 1) + c - '0'; c = GC();
	}
	return x;
}
void write(int x){
	if(x >= 10) write(x / 10);
	PC(x % 10 + '0');
}
int Sub, n, m, hd[2010], a[2000010][2], e[4000010][2];
namespace Sub1{
	int k, mn, ans, b[10][2], dis[10][10];
	void solve(){
		k = 0; mn = 114514; ans = 0;
		int i, j, p, u, v;
		for(i = 1; i <= n; i++){
			for(j = i + 1; j <= n; j++){
				b[k][0] = i; b[k++][1] = j;
			}
		}
		for(i = 0; i < 1 << k; i++){
			for(j = 0, p = 0; j < k; j++){
				if(i >> j & 1) p++;
			}
			if(p != m - 1) continue;
			for(j = 1; j <= n; j++){
				for(p = 1; p <= n; p++) dis[j][p] = n + 1;
			}
			for(j = 0; j < k; j++){
				if(i >> j & 1){
					u = b[j][0]; v = b[j][1];
					dis[u][v] = dis[v][u] = 1;
				}
			}
			for(p = 1; p <= n; p++){
				for(u = 1; u <= n; u++){
					for(v = 1; v <= n; v++) dis[u][v] = min(dis[u][v], dis[u][p] + dis[p][v]);
				}
			}
			for(j = 1, p = 0; j <= m; j++){
				u = a[j][0]; v = a[j][1];
				if(dis[u][v] > n){ p = 114514; break; }
				p += dis[u][v];
			}
			if(p < mn) mn = p, ans = 1;
			else if(p == mn) ans++;
		}
		PC('-'); write(mn); PC(' '); write(ans); PC('\n');
	}
}
//namespace Sub2{
//	void solve(){
//		
//	}
//}
void solve(){
	int i, u, v;
	n = read(); m = read();
	for(i = 1; i <= n; i++) hd[i] = 0;
	for(i = 1; i >> 1 < m; i++){
		a[i + 1 >> 1][0] = u = read(); a[i + 1 >> 1][1] = v = read();
		e[i][0] = hd[u]; e[i][1] = v; hd[u] = i;
		i++;
		e[i][0] = hd[v]; e[i][1] = u; hd[v] = i;
	}
	Sub1::solve();
//	if(Sub <= 2) Sub1::solve();
//	else Sub2::solve();
}
int main(){
	freopen("oi.in", "r", stdin);
	freopen("oi.out", "w", stdout);
	Sub = read();
	int t = read();
	while(t--) solve();
	return 0;
}
